
import java.util.Arrays;

/**
 * @author xianyu
 * @version 1.0
 * @date 2020/9/12 19:27
 */
public class Main3 {
    public static void main(String[] args) {
        int[] arr = {4,3,8,1,2,5,13};
        System.out.println(Arrays.toString(arr));
        QuickSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static int partion(int[] array,int low,int high){//合并排序部分
        int tmp = array[low];
        while(low<high){
            while(low < high && array[high] >= tmp){
                --high;
            }
            if(low >= high){
                break;
            }else{
                array[low] = array[high];//交换小值去前面
            }

            while(low < high && array[low] <= tmp){
                ++low;
            }
            if(low >= high){
                break;
            }else{
                array[high] = array[low];//交换大值去后面
            }
        }
        array[low] = tmp;//枢值归位
        return low;
    }
    static void QuickSort(int[] array){
        //利用一个栈来保存每次需要排序的左右端点信息
        int[] stack = new int[array.length];
        int top = 0;
        int low = 0;
        int high = array.length-1;
        int par = partion(array, low, high);//得到第一个划分点
        if(par > low+1){//左端点是否存在
            stack[top++] = low;
            stack[top++] = par-1;
        }
        if(par < high-1){//左端点是否存在
            stack[top++] = par+1;
            stack[top++] = high;
        }
        while(top > 0){//过程同上，用循环代替递归
            high = stack[--top];
            low = stack[--top];
            par = partion(array, low, high);
            if(par > low+1){
                stack[top++] = low;
                stack[top++] = par-1;
            }
            if(par < high-1){
                stack[top++] = par+1;
                stack[top++] = high;
            }
        }

    }



}
